package JavaCode.lcci;

import JavaCode.linked_list.ListNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * author:fangjie
 * time:2020/3/19
 */
public class N02_06_palindrome_linked_list_lcci {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public boolean isPalindrome(ListNode head) {
        return slove(head,new LinkedList<>());
    }

    private boolean slove(ListNode head, Queue<Integer> queue) {
        if(head==null)return true;
        queue.add(head.val);
        if(!slove(head.next,queue))return false;
        return queue.poll()==head.val;
    }
}
/*
编写一个函数，检查输入的链表是否是回文的。



示例 1：

输入： 1->2
输出： false
示例 2：

输入： 1->2->2->1
输出： true


进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 */
